#include <algorithm>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <bitset>
using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define ForD(i,a,b) for(int i=(a);i>=(b);--i)

typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
const int INF=0xFFFFF;

struct PT{int x,y;PT(int x=0, int y=0):x(x),y(y){}};
int cntp, cntk;
PT ps[11];
PT ks[11];
inline int dist(int x1, int y1, int x2, int y2)
{return max(abs(x1-x2), abs(y1-y2));}
inline void put(int&l, int i, int v)
{
	int m=1;
	m<<=i;
	if(v==1)
		l|=m;
	else
	{
		m=~m;
		l&=m;
	}
}
inline int test(int l, int i)
{
	int m=1;
	m<<=i;
	return m&l;
}
inline bool issub(int pp, int p){return (p-pp)|pp==p;}
inline int remain(int pp, int p){return pp^p;}
int csinglek[1<<10][11];// p set, at p, 11 is for temp, for DP convinience
int get_atp(int atp, int p, int kx=0, int ky=0) // the k is at position p, atp==10 means temp
{
	if(atp!=10)
	{
		kx=ps[atp].x;
		ky=ps[atp].y;
	}
	int& ret=csinglek[p][atp];
	if(atp==10 || ret==-1)
	{
		if(p==0)ret=0;
		else
		{
			ret=INF;
			Rep(i, cntp)
			{
				if(test(p, i))
				{
					int pp=p;
					put(pp, i, 0);
					ret=min(ret,
						dist(kx, ky, ps[i].x, ps[i].y)+get_atp(i, pp));
				}
			}
		}
	}
	return ret;
}
int get(int k, int p) // the cost for single k to eat all pawn in p
{
	int kx=ks[k].x;
	int ky=ks[k].y;
	return get_atp(10, p, kx, ky);
}
int c[11][1<<10];
int go(int k, int p)
{
	int& ret=c[k][p];
	if(ret==-1)
	{
		if(k==0)
			ret=get(0, p);
		else
		{
			int kk=k-1;
			ret=INF;
			For(pp, 0, p)
			{
				if(issub(pp, p))
				{
					int np=remain(pp,p);
					ret=min(ret, go(kk, pp)+get(k, np));
				}
			}
		}
	}
	return ret;
}

class PawnsAndKings {
public:
    int minNumberOfMoves(vector <string> bd) {
		cntk=0;
		cntp=0;
		Rep(i, 8)
			Rep(j, 8)
		{
			if(bd[i][j]=='K')
				ks[cntk++]=PT(j,i);
			else if(bd[i][j]=='P')
				ps[cntp++]=PT(j,i);
		}
		Rep(i, 11) Rep(j, 1<<10) c[i][j]=-1;
		Rep(i, 1<<10)Rep(j, 11) csinglek[i][j]=-1;
        return go(cntk-1, ~((-1)<<cntp)); 
    }

};





// Powered by FileEdit
// Powered by CodeProcessor
